package com.xie.sort.countsort;

import java.util.Arrays;

/**
 * 计数排序
 * <p>
 * O(n)时间复杂度的排序算法
 * <p>
 * 有前提条件，就是待排序的数要满足一定的范围的整数，
 * 而且计数排序需要比较多的辅助空间。
 * <p>
 * 其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。
 * 然后依次输出即可得到有序序列。
 */
public class CountSort {

    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, 56, 22};
        System.out.println("排序前:\n" + Arrays.toString(arr));
        // 计数排序
        countSort(arr);
        System.out.println("排序后:\n" + Arrays.toString(arr));
    }

    public static void countSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        int max = max(arr);

        int[] count = new int[max + 1];
        Arrays.fill(count, 0);

        for (int value : arr) {
            count[value]++;
        }

        int k = 0;
        for (int i = 0; i <= max; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[k++] = i;
            }
        }

    }

    public static int max(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int ele : arr) {
            if (ele > max) {
                max = ele;
            }
        }

        return max;
    }

}
